#include "main/utils.h"
using namespace std;

int getArea1(const vector<vector<int>>& grid,
             vector<vector<int>>& visited,
             int i,
             int j) {
  deque<vector<int>> help_deque;
  help_deque.push_back({i, j});
  visited[i][j] = 1;
  vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  int area = 0;
  while (!help_deque.empty()) {
    auto cur_pos = help_deque.front();
    help_deque.pop_front();
    ++area;
    for (auto dir : dirs) {
      int next_pos_i = cur_pos[0] + dir[0];
      int next_pos_j = cur_pos[1] + dir[1];
      if (next_pos_i >= 0 && next_pos_i < grid.size() &&
          next_pos_j >= 0 && next_pos_j < grid[0].size() &&
          grid[next_pos_i][next_pos_j] &&
          !visited[next_pos_i][next_pos_j]) {
        help_deque.push_back({next_pos_i, next_pos_j});
        visited[next_pos_i][next_pos_j] = 1;
      }
    }
  }
  return area;
}

int getArea2(const vector<vector<int>>& grid,
             vector<vector<int>>& visited,
             int i,
             int j) {
  stack<vector<int>> stack;
  stack.push({i, j});
  visited[i][j] = 1;
  vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  int area = 0;
  while (!stack.empty()) {
    auto cur_pos = stack.top();
    stack.pop();
    ++area;
    for (auto dir : dirs) {
      int next_pos_i = cur_pos[0] + dir[0];
      int next_pos_j = cur_pos[1] + dir[1];
      if (next_pos_i >= 0 && next_pos_i < grid.size() &&
          next_pos_j >= 0 && next_pos_j < grid[0].size() &&
          grid[next_pos_i][next_pos_j] &&
          !visited[next_pos_i][next_pos_j]) {
        stack.push({next_pos_i, next_pos_j});
        visited[next_pos_i][next_pos_j] = 1;
      }
    }
  }
  return area;
}

int getArea3(const vector<vector<int>>& grid,
             vector<vector<int>>& visited,
             int i,
             int j) {
  int area = 1;
  visited[i][j] = 1;
  vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  for (auto dir : dirs) {
    int next_pos_i = i + dir[0];
    int next_pos_j = j + dir[1];
    if (next_pos_i >= 0 && next_pos_i < grid.size() &&
        next_pos_j >= 0 && next_pos_j < grid[0].size() &&
        grid[next_pos_i][next_pos_j] &&
        !visited[next_pos_i][next_pos_j]) {
      area += getArea3(grid, visited, next_pos_i, next_pos_j);
    }
  }
  return area;
}

int maxLand(const vector<vector<int>>& grid, decltype(getArea1) func) {
  int row = grid.size();
  int col = grid[0].size();
  vector<vector<int>> visited;
  visited.resize(row);
  for (int i = 0; i < visited.size(); ++i) {
    visited[i].resize(col, 0);
  }
  int max_area = 0;
  for (int i = 0; i < row; ++i) {
    for (int j = 0; j < col; ++j) {
      if (grid[i][j] && !visited[i][j]) {
        int tmp_area = func(grid, visited, i, j);
        max_area = max(max_area, tmp_area);
      }
    }
  }
  return max_area;
}

int numLand(const vector<vector<int>>& grid, decltype(getArea1) func) {
  int row = grid.size();
  int col = grid[0].size();
  vector<vector<int>> visited;
  visited.resize(row);
  for (int i = 0; i < visited.size(); ++i) {
    visited[i].resize(col, 0);
  }
  int num_land = 0;
  for (int i = 0; i < row; ++i) {
    for (int j = 0; j < col; ++j) {
      if (grid[i][j] && !visited[i][j]) {
        func(grid, visited, i, j);
        ++num_land;
      }
    }
  }
  return num_land;
}

int main() {
  vector<vector<int>> grid = {{1, 1, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 1, 0, 1, 0}, {0, 0, 1, 0, 0}};
  cout << maxLand(grid, getArea1) << endl;
  cout << maxLand(grid, getArea2) << endl;
  cout << maxLand(grid, getArea3) << endl;

  cout << numLand(grid, getArea1) << endl;
  cout << numLand(grid, getArea2) << endl;
  cout << numLand(grid, getArea3) << endl;

  return 0;
}
